package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/replace-non-coprime-numbers-in-array/
 * @create 2025/10/26 13:53
 * @since JDK17
 */

public class Solution60 {
    int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
    int lcm(int x, int y) {
        return ((int) ((long) x / gcd(x, y) * y));
    }

    public List<Integer> replaceNonCoprimes(int[] nums) {
        List<Integer> stack = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (!stack.isEmpty() && gcd(stack.get(stack.size() - 1), x) > 1) {   // 要去除
                x = lcm(x, stack.remove(stack.size() - 1));
            }
            stack.add(x);
        }
        return stack;
    }
}
